package com.tyrone.algorithm.sort;

public class Quick {
    /**
     * 对数组内的元素进行排序
     * @param a
     */
    public static void sort(Comparable[] a){
        int lo=0,hi=a.length-1;
        sort(a,lo,hi);
    }

    /**
     * 对数组a中从索引lo到索引hi之间的元素进行排序
     * @param a
     * @param lo
     * @param hi
     */
    private static void sort(Comparable[] a, int lo, int hi){
        if (lo>=hi){
            return;
        }
        int partition = partition(a, lo, hi);
        sort(a,lo,partition);
        sort(a,partition+1,hi);
    }

    /**
     *  对数组a中，从索引 lo到索引 hi之间的元 素进行分组，并返回分组界限对应的索引
     * @param a
     * @param lo
     * @param hi
     * @return
     */
    public static int partition(Comparable[] a,int lo,int hi){
        Comparable comparable = a[lo];
        int left=lo;
        int right=hi+1;
        while (true){
            while(less(comparable,a[--right])){
                if (right==lo){
                    break;
                }
            }
            while (less(a[++left],comparable)){
                if (left==hi){
                    break;
                }
            }
            if (left>=right){
                break;
            }else{
                exch(a,left,right);
            }
        }
        exch(a,lo,right);
        return right;
    }
    /**
     * 判断v是否小于w
     * @param v
     * @param w
     * @return
     */
    private static boolean less(Comparable v,Comparable w){
        return v.compareTo(w)<0;
    }


    /**
     * 交换a数组中，索引i和索引j处的值
     * @param a
     * @param i
     * @param j
     */
    private static void exch(Comparable[] a,int i,int j){
        Comparable t ;
        t=a[i];
        a[i]=a[j];
        a[j]=t;
    }
}
